/**
 * 416. 分割等和子集
 */
public class Solution_416 {
    /**
     * 官方题解：动态规划（不太懂）
     * <p>
     * 时间复杂度：O(N * target)，N 为数组长度，target 为数组和的一半
     * <p>
     * 空间复杂度：O(N * target)，N 为数组长度，target 为数组和的一半
     */
    public boolean canPartition(int[] nums) {
        int len = nums.length;
        if (len < 2) {
            return false;
        }

        // 计算数组和，以及找出数组中的最大值
        int sum = 0, maxNum = nums[0];
        for (int i = 0; i < len; i++) {
            sum += nums[i];
            maxNum = nums[i] > maxNum ? nums[i] : maxNum;
        }
        // 如果 sum 是奇数，则无法划分
        if (sum % 2 != 0) {
            return false;
        }
        int target = sum / 2;
        // 如果 maxNum > target，也无法划分
        if (maxNum > target) {
            return false;
        }

        // dp[i][j] 表示从数组的 [0,i] 下标范围内选取若干个正整数（可以是 0 个），
        // 是否存在一种选取方案使得被选取的正整数的和等于 j
        boolean[][] dp = new boolean[len][target + 1];
        for (int i = 0; i < len; i++) {
            dp[i][0] = true;
        }
        dp[0][nums[0]] = true;
        for (int i = 1; i < len; i++) {
            int num = nums[i];
            for (int j = 1; j <= target; j++) {
                if (j >= num) {
                    dp[i][j] = dp[i - 1][j] | dp[i - 1][j - num];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[len - 1][target];
    }

    public static void main(String[] args) {
        Solution_416 solution = new Solution_416();
        int[] nums = new int[] { 1, 5, 11, 5 };
        boolean ans = solution.canPartition(nums);
        System.out.println(ans);
        nums = new int[] { 1, 2, 3, 5 };
        ans = solution.canPartition(nums);
        System.out.println(ans);
    }
}
